package com.ccsoft.leetcode.service;

import org.springframework.stereotype.Service;

import java.util.*;

/**
 * 2021年11月3日 08:32:32 chanchaw
 * 有效括号
 * 1. 字符串长度必须是偶数，奇数的话直接返回 false 退出
 * 2. 采用栈数据结构来对应括号
 * 3. 最后栈内没有
 */
@Service
public class Brackets {

    public boolean isValid(String s) {
        if( s.length() == 0 ) return false;
        if( s.length() % 2  == 1 ) return false;// 必须是偶数个，奇数个则必定是无效的括号，直接返回 false

        Deque<String> deque = new ArrayDeque<>();
        for(int i = 0;i<s.length();i++){
            String singleBracket = s.substring(i,i+1);
            if(leftOrRight(singleBracket) == 0){
                deque.addLast(singleBracket);
            }else {
                if( i == 0 ) return false;// 第一个就是右边的括号则直接判定为无效
                String ele = deque.pollLast();
                if( ele == null ) return false;
                String rightBracket = getRightBracket(ele);
                if(  !rightBracket.equals(singleBracket) ) return false;
            }
        }

        return deque.size() <=0 ? true:false;
    }

    private String getRightBracket(String s){
        Map<String,String> allMap = getMap();
        for(String key:allMap.keySet()){
            if( key.equals(s) ) {
                return allMap.get(s);
            }
        }

        return null;
    }

    private Map<String,String> getMap(){
        Map<String,String> map = new HashMap<>();
        map.put("(",")");
        map.put("[","]");
        map.put("{","}");
        return map;
    }

    private int leftOrRight(String s){
        int ret = 0;
        switch (s){
            case ")":
                ret = 1;
                break;
            case "]":
                ret = 1;
                break;
            case "}":
                ret = 1;
                break;
            default:
                ret = 0;
        }
        return ret;
    }
}
